package 归并算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Classname countSmaller315
 * @Description TODO
 * @Date 2022/2/15 20:59
 * @Created by xjl
 */
public class countSmaller315 {

    List<Integer> ans = new ArrayList<>(); //记录最终的结果
    int[] index; //原数组的索引数组，存储着原数组中每个元素对应的下标
    int[] count; //记录题目中所求的count[i]

    public List<Integer> countSmaller2(int[] nums) {
        int len = nums.length;
        index = new int[len];
        count = new int[len];
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        mergeSort(nums, 0, nums.length - 1);
        return Arrays.stream(count).boxed().collect(Collectors.toList());
    }

    public void mergeSort(int[] a, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);
        merge(a, l, mid, r);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int P1 = start;
        int P2 = mid + 1;
        int cur = 0;

        int[] tmp = new int[end - start + 1]; //临时数组用于存储一次归并过程中排序好的元素，

        int[] tmpIndex = new int[end - start + 1];//临时数组的索引数组，存储这临时数组中每个元素对应的下标

        while (P1 <= mid && P2 <= end) {
            if (nums[P1] > nums[P2]) {
                count[index[P1]] += end - P2 + 1; //右半部分小于nums[P1]元素的数目
                tmpIndex[cur] = index[P1]; //记录元素位置的改变
                tmp[cur] = nums[P1];
                P1++;
            } else {
                tmp[cur] = nums[P2];
                tmpIndex[cur] = index[P2];
                P2++;
            }
            cur++;
        }
        while (P1 <= mid) {
            tmp[cur] = nums[P1];
            tmpIndex[cur] = index[P1];
            P1++;
            cur++;
        }
        while (P2 <= end) {
            tmp[cur] = nums[P2];
            tmpIndex[cur] = index[P2];
            P2++;
            cur++;
        }
        for (int i = 0; i < end - start + 1; i++) {
            nums[i + start] = tmp[i];
            index[i + start] = tmpIndex[i];
        }
    }
}
